<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="mdZ9F" id="mdZ9F"><span data-lake-id="u79c350eb" id="u79c350eb">典型回答</span></h1>
  <p data-lake-id="u6eb0fceb" id="u6eb0fceb"><span data-lake-id="u08268bf9" id="u08268bf9">栈和队列从定义上来讲，只有一个不同，就是</span><strong><span data-lake-id="u4b86552e" id="u4b86552e">栈是先进后出的，而队列是先进先出的。</span></strong><span data-lake-id="uda212fb5" id="uda212fb5">网上有一个形象的例子，说栈是吃了吐，队列则是吃了拉，哈哈哈。两者不的不同如下所图所示：</span></p>
  <p data-lake-id="u7615f47c" id="u7615f47c"><span data-lake-id="ud6c2791b" id="ud6c2791b">​</span><br></p>
  <p data-lake-id="u343c45f4" id="u343c45f4"><span data-lake-id="ue71813fe" id="ue71813fe">栈：</span></p>
  <p data-lake-id="u15a57ca4" id="u15a57ca4"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676790647250-0ddc1a49-ab70-490a-b3ca-5be0a13dd491.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_13%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ufd7d8f4b" id="ufd7d8f4b"><span data-lake-id="ub599f503" id="ub599f503">​</span><br></p>
  <p data-lake-id="u395837b1" id="u395837b1"><span data-lake-id="u68a0708e" id="u68a0708e">队列：</span></p>
  <p data-lake-id="ud9ebbafd" id="ud9ebbafd"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676790653577-0e2e3f8f-20e1-4295-a8a2-3099985fad0d.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_15%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"><span data-lake-id="u03f69351" id="u03f69351">​</span></p>
  <h2 data-lake-id="ZOGSN" id="ZOGSN"><span data-lake-id="u788539db" id="u788539db">栈和队列的实现</span></h2>
  <p data-lake-id="u72be88f5" id="u72be88f5"><span data-lake-id="u877169df" id="u877169df">从实现上来说，栈和队列都可以用数组或者链表实现，不过从实现难度和时空复杂度的角度考虑，一般来说，栈会用数组实现，队列会用链表实现。如下所示：</span></p>
  <pre lang="java"><code>
class StackByArray {
    private int top = -1;
    private int maxSize;
    private int[] stack;

    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    public boolean isFull(){
        return top == maxSize - 1;
    }

    public boolean isEmpty(){
        return top == -1;
    }

    public void push(int data){
        if (isFull()){
            return;
        }
        stack[++top] = data;
    }

    public int pop () {
        if (isEmpty()){
            throw new RuntimeException("this stack is empty");
        }
        int data = stack[top--];
        return data;
    }
}
class StackByLink {

    private Node head;

    public void push(int data) {
        Node temp = new Node(data);
        if(head != null) {
            temp.next = head;
        }
        head = temp;
    }

    public int pop() {
        if(head == null) {
            return 0;
        }
        int ans = head.data;
        head = head.next;
        return ans;
    }

    private static class Node {
        public int data;
        public Node next;
        public Node(int data) {
            this.data = data;
        }
    }
}
</code></pre>
  <p data-lake-id="ub9b86152" id="ub9b86152"><span data-lake-id="u3a2e7d55" id="u3a2e7d55">​</span><br></p>
  <pre lang="java"><code>
class QueueByLink {
    
    Node front;
    Node tail;
    int size;
    
    public void offer(int data){
        Node temp = new Node(data);
        if(isEmpty()){
            front = temp;
            tail = front;
        } else {
            tail.next = temp;
        	tail = temp;
        }
        size++;
    }

    public int poll(){
        if(isEmpty()){
            return 0;
        }
        int data = front.data;
        front = front.next;
        size --;
        return data;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    private static class Node {
        public int data;
        public Node next;
        public Node(int data) {
            this.data = data;
        }
    }
}
</code></pre>
  <p data-lake-id="u64712d18" id="u64712d18"><span data-lake-id="u9529adea" id="u9529adea">在Java中，常见的栈有Stack，Deque(implemented by LinkedList&#x0;)，常见的队列有Queue和Queue（implemented by LinkedList）所以我们一般刷题的时候，常常会用下面的写法：</span></p>
  <pre lang="java"><code>
Stack&lt;Integer&gt; stack = new Stack&lt;&gt;();
stack.push(1);
stack.pop();
Queue&lt;Integer&gt; queue = new LinkedList&lt;&gt;();
queue.offer(1);
queue.poll();
</code></pre>
  <h2 data-lake-id="I9HGc" id="I9HGc"><span data-lake-id="u65c515c5" id="u65c515c5">应用</span></h2>
  <p data-lake-id="u3f7d9f1d" id="u3f7d9f1d"><span data-lake-id="u7a3552a7" id="u7a3552a7">栈和队列在日常开发过程中无处不在。</span></p>
  <p data-lake-id="u4a5441e3" id="u4a5441e3"><span data-lake-id="u66da21e5" id="u66da21e5">​</span><br></p>
  <p data-lake-id="u7c52e434" id="u7c52e434"><strong><span data-lake-id="u3a0b1d3b" id="u3a0b1d3b">我们平常所使用的递归，就是通过栈来实现的</span></strong><span data-lake-id="u1e2baee4" id="u1e2baee4">。同时还有JVM中的方法在执行的时候，也会放到栈上，因为他们的执行顺序都是遵循先进后出的</span></p>
  <p data-lake-id="ud95aff4a" id="ud95aff4a"><span data-lake-id="ub6730cab" id="ub6730cab">​</span><br></p>
  <p data-lake-id="ue08bbc72" id="ue08bbc72"><strong><span data-lake-id="u4a97a76d" id="u4a97a76d">队列常常作为缓冲区来使用，像我们熟知的生产者和消费者模型</span></strong><span data-lake-id="u588b15c7" id="u588b15c7">，生产者完成任务后，会把数据存放到队列中，等待消费者来读取。</span></p>
  <h1 data-lake-id="yxjA9" id="yxjA9"><span data-lake-id="uc2988958" id="uc2988958">知识扩展</span></h1>
  <h2 data-lake-id="XvrB3" id="XvrB3"><span data-lake-id="u5ab07f8b" id="u5ab07f8b">什么是双端队列和循环队列</span></h2>
  <h3 data-lake-id="p1pR5" id="p1pR5"><span data-lake-id="ub8022841" id="ub8022841">双端队列</span></h3>
  <p data-lake-id="u4946d607" id="u4946d607"><span data-lake-id="uc8003477" id="uc8003477">队列还有一种变形的结构叫双端队列，所谓的双端，就是说该队列不仅遵循FIFO原则，通常也可以按照使用者的想法从队首或者队尾进行插入和删除</span></p>
  <pre lang="java"><code>
Deque&lt;Integer&gt; deque = new LinkedList&lt;&gt;();
deque.offerFirst(1);
deque.offerLast(1);
deque.pollFirst();
deque.pollLast();
</code></pre>
  <h3 data-lake-id="cuRGo" id="cuRGo"><span data-lake-id="ud6ec3593" id="ud6ec3593">循环队列</span></h3>
  <p data-lake-id="uc83a8be9" id="uc83a8be9"><span data-lake-id="ud0d06fae" id="ud0d06fae">一般情况下，数组是不能实现队列的，因为先进先出，可能会存在假溢出的情况，所以数组的空间一定会被浪费。所以，我们会通过循环的方式，当最尾部的索引到达length之后，我们会将该索引重新置为0，以此来重复利用数组的空间。而这样一种形式，就会造成一种逻辑循环，也就是我们说的循环队，假溢出如下所示：</span></p>
  <p data-lake-id="u7adfc237" id="u7adfc237"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676788860101-aeb0e7db-0a5d-414e-b941-617d963dcb2e.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_36%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u5653a42f" id="u5653a42f"><span data-lake-id="ucd174a65" id="ucd174a65">代码如下：</span></p>
  <pre lang="java"><code>
class QueueByArray {
	private final int[] items;
	private int head=0;
	private int tail=0;
    
	public boolean push(int data) {
		if(((tail + 1) % items.length) == head) {
            // 此时说明队列的空间已经满了，只能扩容
			return false;
		}
		else {	
			items[tail] = data;
			tail = (tail+1) % items.length;
			return true;
		}
	}
	public int pop() {
		int data = items[head];
		head = (head+1) % items.length;
		return data;
	}
	public QueueByArray(int length) {
		this.items = new int[length];
    }
}
</code></pre>
  <p data-lake-id="ucea54141" id="ucea54141"><span data-lake-id="ud5e83f17" id="ud5e83f17">一般来说，循环队列可以作为缓冲区使用，如果index超出，直接覆盖就可以了。</span></p>
  <p data-lake-id="u7e55d2af" id="u7e55d2af"><span data-lake-id="u700758fb" id="u700758fb">​</span><br></p>
  <h2 data-lake-id="XFFah" id="XFFah"><span data-lake-id="u85ab11fc" id="u85ab11fc">栈实现队列</span></h2>
  <p data-lake-id="ue3619e0e" id="ue3619e0e"><br></p>
  <h2 data-lake-id="YDcxP" id="YDcxP"><span data-lake-id="u593e6bc5" id="u593e6bc5">队列实现栈</span></h2>
  <p data-lake-id="ue1aa3ab4" id="ue1aa3ab4"><br></p>
  <h2 data-lake-id="UAtSq" id="UAtSq"><span data-lake-id="udd520cf6" id="udd520cf6">相关算法</span></h2>
  <ol list="u26e5313b">
   <li fid="u3b30f21c" data-lake-id="ud15d82b8" id="ud15d82b8"><span data-lake-id="udb833461" id="udb833461">用栈实现队列：</span><a href="https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/" target="_blank" data-lake-id="ue1edbccf" id="ue1edbccf"><span data-lake-id="uacc78843" id="uacc78843">https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/</span></a></li>
   <li fid="u3b30f21c" data-lake-id="u1d5ee518" id="u1d5ee518"><span data-lake-id="u2de410de" id="u2de410de">用队列实现栈：</span><a href="https://leetcode.cn/problems/implement-stack-using-queues/" target="_blank" data-lake-id="uf0f5ce15" id="uf0f5ce15"><span data-lake-id="ub66096b6" id="ub66096b6">https://leetcode.cn/problems/implement-stack-using-queues/</span></a></li>
   <li fid="u3b30f21c" data-lake-id="u8636d1c7" id="u8636d1c7"><span data-lake-id="u2d6fd95a" id="u2d6fd95a">最小栈：</span><a href="https://leetcode.cn/problems/min-stack/" target="_blank" data-lake-id="u678165c8" id="u678165c8"><span data-lake-id="uec84ac00" id="uec84ac00">https://leetcode.cn/problems/min-stack/</span></a></li>
   <li fid="u3b30f21c" data-lake-id="u43543ca9" id="u43543ca9"><span data-lake-id="ud8c0f9c0" id="ud8c0f9c0">双端队列：</span><a href="https://leetcode.cn/problems/design-circular-deque/" target="_blank" data-lake-id="uc68a55ca" id="uc68a55ca"><span data-lake-id="u71fceeb2" id="u71fceeb2">https://leetcode.cn/problems/design-circular-deque/</span></a></li>
  </ol>
  <p data-lake-id="u13cded39" id="u13cded39"><span data-lake-id="u9fbe8f9d" id="u9fbe8f9d">​</span><br></p>
 </body>
</html>